\section{Partial backup scheme}\label{pbackup}
In this section, we present our partial backup scheme design. We first give the energy efficiency analysis and to support the patrial backup mechanism in energy reduction. Then we present the design details of SBDP, including the theory basis and algorithm design.

\subsection{Partial backup overview}
Our partial backup scheme is based on the principle of dead-block prediction. Only a fraction of data in cache blocks will be referenced again before evictions. A cache line that will be referenced before eviction is often referred to a \emph{live block}, otherwise a \emph{dead block}. Predicting dead blocks before eviction can improve cache efficiency. Dead-block prediction has been used in some cache optimization fields such as data prefetching, replacement algorithm design, data bypassing, power management, etc.

\begin{figure}[!hpt]
\centering
\includegraphics[scale = 0.33]{classification.pdf}
\caption{Scenarios of live blocks and dead blocks}\label{classification}
\end{figure}

Fig.~\ref{classification}(a) represents two scenarios of live blocks. After a cache block is filled, it is accessed by the CPU and its lifetime is prolonged beyond the backup point. Therefore, it needs backup because data in the cache block will be accessed after restore. Otherwise, extra cache misses will be introduced. Another live block case occurs when the block has been overwritten and marked as dirty block before the backup point. The block should be backed up otherwise the CPU and cache will be asynchronous thus incurs a system error. Fig.~\ref{classification}(b) represents the scenario of dead blocks. The dead period is defined as the time interval between two successive cache lifetime. If a cache block is in a dead period at the backup point, then data in it do not need to be backed up since it will not be referenced again after restoration.

\input{tab_parameter}

We further give the energy efficiency analysis of the partial backup scheme. Tab.~\ref{Parameters} shows the parameters and definitions used in our analysis. Energy consumed in full backup process is expressed as follows.
\begin{equation}\label{eq1}
  E_{fb} = (N_d+N_l)E_b
\end{equation}
While energy consumed in partial backup process is
\begin{equation}\label{eq1}
  E_{pb} = E_{bdp} + N_dE_b
\end{equation}
If the partial backup scheme is more energy efficient than the full backup scheme, the following inequation should be satisfied.
\begin{equation}\label{eq1}
  E_{pb} < E_{fb}
\end{equation}
That is
\begin{equation}\label{eq1}
    E_{bdp}<N_lE_b
\end{equation}
We note that the amount of energy reduction is expressed as $\bigtriangleup E = N_lE_b - E_{dbp}$, thus a low power dead-block predictor is required.

\subsection{SBDP: Theory basis}
We use a statistics based dead block predictor to achieve low power dead-block prediction. The core theory basis lies in the correlation between recently used bits (RUB) distribution and dead/live block classification. RUB is used in caches adopting the LRU based replacement algorithm. It represents the order of usage for each cache block in a set.

\begin{figure}[!hpt]
\centering
\subfigure[Patricia]{\label{Patricia}\includegraphics[height=1.05in, width=1.5in]{Patricia.pdf}}
\subfigure[qsort\_large]{\label{qsortlarge}\includegraphics[height=1.05in, width=1.5in]{qsortlarge.pdf}}
\subfigure[qsort\_small]{\label{qsortsmall}\includegraphics[height=1.05in, width=1.5in]{qsortsmall.pdf}}
\subfigure[typeset]{\label{typeset}\includegraphics[height=1.05in, width=1.5in]{typeset.pdf}}
\caption{Block proportion for different LRU bits}\label{LRU}
\end{figure}

Fig.~\ref{LRU} shows the proportion of dead blocks and live blocks with different RUB when running 4 benchmarks from Mibench~\cite{Mibench} on a four-way associated cache. Note that we have ignored dirty blocks because they are definitely alive. Note that cache blocks with larger RUB are referenced longer time before. From fig.~\ref{LRU}, we notice that the block type distribution shows different properties with the change of RUB. For example, considering benchmark patricia as shown in fig.~\ref{Patricia}, all cache blocks of RUB=0 and RUB=1 are live. Blocks of RUB=2 have more than $\frac{1}{2}$ probability to be live, while almost all block of RUB=4 are dead. Based on the information, we can predict that all cache blocks of RUB=3 are dead at the backup point and discard them. What's more, block type proportion varies across benchmarks. Hence statistical information needs dynamic updating.


\subsection{Algorithm of statistics based dead-block prediction}
\input{prealgo}
Having the predictor architecture, we describe the algorithm of SBDP. We give the algorithm flow, followed by the threshold selection analysis. Algorithm~\ref{alg} descries the algorithm of SBDP. The input of the a cache block set $\{C_i\},i=1,2,...N$ where N is the number of cache blocks and the dead block proportions for each RUB $\{R_j\},j=1,2,...M$, where M is the degree of association. Another input is the death sentence threshold $D_{th}$. The output is the state judgement $S$ (dead or live) for each cache block. Line 1 initials $S_i$ to live for each cache block and the death sentance flag to zero for each RUB. Line 2 to 5 determines whether cache blocks with the corresponding RUB should be sentenced to death by comparing the dead block proportion with the death threshold $D_{th}$. Line 7 to 11 scans all cache lines and make the death judgement. The if statement in line 8 is based on the principle that dirty lines are surely alive and lines with a death sentenced RUB are predicted to to dead.

\subsection{Circuit implementation}
We further give the circuit implementation of SBDP as shown in fig.~\ref{SBDP}

\begin{figure}[!hpt]
\centering
\includegraphics[scale = 0.33]{SBDP.pdf}
\caption{Circuit of the statistics based predictor}\label{SBDP}
\end{figure}

Fig.~\ref{SBDP} depicts the circuit implementation of the SBDP in a 4-way associated cache. Two 4$\times$N bit counter array are used to count the number of dead blocks and total sampled blocks respectively. Each entry is used to count the dead blocks for each RUB. After restoration, if a dead block is detected, then the corresponding dead block counter and the sampled block counter is increased by 1. Oppositely, if a live bit block with RUB=i is detected, then only the corresponding counter i in the sampled block counter is increased by 1. Assuming that for RUB=1, the dead-block counter=N and the sampled block counter=M, then $D_{th} \times M < N$ indicates that the if statement in line 8 of algorithm~\ref{alg} is satisfied. The comparison is implemented by a multiplier and a N-bit comparator. Ambient logics is designed to compute the following logic:

\begin{equation}\label{equa1}
    Dead \ bit = \overline{VB}\| Result \&\& \overline{DB}
\end{equation}

Where VB represents to the valid bit, DB is the dirty bit and result is the output of the comparator. Dead bit is set when the cache block is predicted to be dead. When the backup\_enable signal is set, the prediction result is written into the dead bit region.


